package features.advance.leetcode.interview.offer.easy;

/**
 *  剑指 Offer 10- I. 斐波那契数列
 *
 *  难度：简单
 *
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：5
 *
 *
 * 提示：
 *
 * 0 <= n <= 100
 *
 * @author LIN
 * @date 2021-05-13
 */
public class Offer10_1 {
    public int fib(int n) {
        if(n<0){
            return 0;
        }
        if(n == 1 || n==2){
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        Offer10_1 offer10_1 = new Offer10_1() {

            @Override
            public int fib(int n) {
                if(n==0){
                    return 0;
                }else if(n == 1){
                    return 1;
                }
                int[] dp = new int[n+1];
                dp[0] = 0;
                dp[1] = 1;
                //双指针也可以解决这个问题
                for (int i = 2; i <= n; i++) {
//                    dp[i] = dp[i-2]+dp[i-1];
                    dp[i] = (dp[i-2] % 1000000007+dp[i-1] % 1000000007) % 1000000007;
                }
                return dp[n];
            }
        };
        int fib = offer10_1.fib(45);
        System.out.println(fib);
    }
}
